package com.caoyanan.algorithm.question.zuoTraining.training003.class08;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;

/**
 * int[] d，d[i]：i号怪兽的能力
 * int[] p，p[i]：i号怪兽要求的钱
 * 开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的怪兽。
 * 如果你当前的能力，小于i号怪兽的能力，你必须付出p[i]的钱，贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上；
 * 如果你当前的能力，大于等于i号怪兽的能力，你可以选择直接通过，你的能力并不会下降，
 * 你也可以选择贿赂这个怪兽，然后怪兽就会加入你，他的能力直接累加到你的能力上。
 * 返回通过所有的怪兽，需要花的最小钱数。
 * @author: caoyanan
 * @time: 2021/5/24 5:33 下午
 */
public class Question01_FightMonsters {

    public static void main(String[] args) {

        /**
         * 错误原因 dp[i-1][j] >= abilities[i] 少了一个等于
         */
        int i2 = abilityVeryBig(new int[]{3544, 1360, 4904}, new int[]{3, 4, 6});
        System.out.println("怪兽需要的能力是:[3544, 1360, 4904], 怪兽需要的钱:[3, 4, 6], 最少的钱"+i2);

        /**
         * 错误原因 i <= sumMoney;少了一个等于
         */
        int i1 = abilityVeryBig(new int[]{33, 325, 428}, new int[]{572, 838, 987});
        System.out.println("怪兽能力(33,325,428) 需要的钱(572,838,987) 最少的钱为:"+i1);
        int count = 100000;
        for (int i = 0; i < count; i++) {
            int monstersCount = 3;
            int maxAbility = 5000;
            int maxNeedMoney = 1000;
            int[] abilities = LogarithmInputGenerator.getInstance().generateRandomArray(monstersCount, maxAbility);
            int[] needMoneys = LogarithmInputGenerator.getInstance().generateRandomSortArray(monstersCount, maxNeedMoney);
            long atLeastNeedMoney3 = recursion(abilities, needMoneys, 0, 0);
            int atLeastNeedMoney = needMoneyVeryBig(abilities, needMoneys);
            int atLeastNeedMoney2 = abilityVeryBig(abilities, needMoneys);
            if (atLeastNeedMoney3 != atLeastNeedMoney || atLeastNeedMoney != atLeastNeedMoney2) {
                System.out.printf("怪兽需要的能力是:%s, 怪兽需要的钱:%s，递归值:%s, 能力动态规划:%s，钱数动态规划:%s\n",
                        Arrays.toString(abilities), Arrays.toString(needMoneys),
                        atLeastNeedMoney3, atLeastNeedMoney, atLeastNeedMoney2);
            }

        }
    }

    /**
     * 递归。
     * @param abilities 怪兽能力
     * @param needMoneys 需要的钱
     * @param index 当前是第几个怪兽
     * @param alreadyHaveAbility 当前拥有的能力
     * @return
     */
    private static long recursion(int[] abilities, int[] needMoneys, int index, int alreadyHaveAbility) {
        //如果到最后了，已经没有怪兽了，就不需要钱了。
        if (index == abilities.length) {
            return 0;
        }
        if (alreadyHaveAbility < abilities[index]) {
            return needMoneys[index] + recursion(abilities, needMoneys,
                    index + 1, alreadyHaveAbility + abilities[index]);
        }
        //把怪兽吓走
        long passDirectly = recursion(abilities, needMoneys, index + 1, alreadyHaveAbility);
        //花钱贿赂
        long useMoney = needMoneys[index] + recursion(abilities, needMoneys,
                index+1, alreadyHaveAbility + abilities[index]);
        return Math.min(passDirectly, useMoney);
    }

    /**
     * 需要的钱特别巨大，怪兽的能力在500以内
     * dp[i][j] 表示从i个怪兽开始搞定往后所有的，能力是j的情况下，最少需要多少钱。
     * @param abilities
     * @param needMoneys
     * @return
     */
    private static int needMoneyVeryBig(int[] abilities, int[] needMoneys) {
        int abilitySum = abilities[0];
        for (int i = 1; i < abilities.length; i++) {
            abilitySum+=abilities[i];
        }
        int[][] dp = new int[abilities.length+1][abilitySum + 1];
        for (int i = abilities.length-1; i >= 0; i--) {
            for (int j = 0; j <= abilitySum; j++) {
                if (j + abilities[i] > abilitySum) {
                    continue;
                }
                if (j < abilities[i]) {
                    dp[i][j] = needMoneys[i] + dp[i+1][j+abilities[i]];
                } else {
                    dp[i][j] = Math.min(dp[i+1][j], needMoneys[i] + dp[i+1][j+abilities[i]]);
                }
            }
        }
        return dp[0][0];
    }

    /**
     * 怪兽能力特别巨大，需要的钱在500以内
     * dp[i][j], 表示搞定从0开始搞定i个怪兽，花了j钱的情况下，可以拥有的最大能力，-1表示不能够完成这件事情
     * 最后一行的最左侧不为-1的列数j，就是答案
     * @param abilities
     * @param needMoneys
     * @return
     */
    private static int abilityVeryBig(int[] abilities, int[] needMoneys) {
        int sumMoney = needMoneys[0];
        for (int i = 1; i < needMoneys.length; i++) {
            sumMoney += needMoneys[i];
        }
        int[][] dp = new int[abilities.length][sumMoney + 1];
        for (int i = 0; i < abilities.length; i++) {
            for (int j = 0; j <= sumMoney; j++) {
                dp[i][j] = -1;
            }
        }

        //第一批怪兽，一定要花钱
        dp[0][needMoneys[0]] = abilities[0];
        for (int i = 1; i < abilities.length; i++) {
            for (int j = 0; j <= sumMoney; j++) {
                //当用钱的时候,上一个用 j-needMoneys[i]的钱能搞定
                if ( j >= needMoneys[i] && dp[i-1][j-needMoneys[i]] != -1) {
                    dp[i][j] = dp[i-1][j-needMoneys[i]] + abilities[i];
                }
                //第i个怪兽，不用钱。那i-1个怪兽花了j钱的能力必须大于i怪兽的能力
                if (dp[i-1][j] >= abilities[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                }
            }
        }

        //最后一行不为-1的答案
        for (int i = 0; i <= sumMoney; i++) {
            if (dp[abilities.length - 1][i] != -1) {
                return i;
            }
        }
        return 0;
    }
}
